package day01

// 122. 买卖股票的最佳时机 II
//
// https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
//
// ```go
func maxProfit(prices []int) int {
	ans := 0
	for i := 1; i < len(prices); i++ {
		if prices[i] > prices[i-1] {
			ans += prices[i] - prices[i-1]
		}
	}
	return ans
}
func maxProfit(prices []int) int {
	dp := make([][2]int, len(prices))
	dp[0][0] = 0
	dp[0][1] = -prices[0]
	for i := 1; i < len(prices); i++ {
		dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
		dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
	}
	return dp[len(prices)-1][0]
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// ```
//
// 55. 跳跃游戏
//
// https://leetcode.cn/problems/jump-game/
//
// ```go
func canJump(nums []int) bool {
	maxPos := 0
	for i := 0; i < len(nums); i++ {
		if i <= maxPos {
			maxPos = max(maxPos, i+nums[i])
			if maxPos >= len(nums)-1 {
				return true
			}
		}
	}
	return false
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// ```
//
// 45. 跳跃游戏 II
//
// https://leetcode.cn/problems/jump-game-ii/
//
// ```go
func jump(nums []int) int {
	maxPos, end := 0, 0
	steps := 0
	for i := 0; i < len(nums)-1; i++ {
		maxPos = max(maxPos, i+nums[i])
		if i == end {
			end = maxPos
			steps++
			if maxPos > len(nums)-1 {
				break
			}
		}
	}
	return steps
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

//```
